package hashtables;

import hashtables.Entries.Entry;
import java.util.LinkedList;

/**
 *
 * @author Jan, Konstantin
 * @version 1.0
 */
public class Hashtable
{
    private int _capacity;
    private int _size;
    private double _loadFactor;
    private int _threshold;
    private LinkedList<Entry>[] _table;
    
    /**
     * Creates a hashtable
     * @param capacity The initial capacity of the hashtable
     * @param loadFactor The load factor of the hashtable (must be greater than 0)
     */
    public Hashtable(int capacity, double loadFactor)
    {
        if (capacity <= 0)
        {
            capacity = 1;
        }
        
        if (loadFactor <= 0.0)
        {
            loadFactor = 0.75;
        }
        
        _capacity = capacity;
        _size = 0;
        _loadFactor = loadFactor;
        
        _table = (LinkedList<Entry>[])new LinkedList[_capacity];
        
	_threshold = (int)(_capacity * _loadFactor);
    }
    
    /**
     * Hashes a value
     * @param value The value
     * @return The hashed value
     */
    private int hashValue(int value)
    {
        return hashValue(value, _capacity);
    }
    
    /**
     * Hashes a value
     * @param value The value
     * @param capacity The capacity
     * @return The hashed value
     */
    private int hashValue(int value, int capacity)
    {
        return value % capacity;
    }
    
    /**
     * Doubles the size of the hashtable
     */
    private void expandHashtable()
    {
        expandHashtable(2);
    }
    
    /**
     * Expands the size of the hashtable
     * @param factor The new capacity is oldCapacity * factor
     */
    private void expandHashtable(int factor)
    {
        LinkedList<Entry>[] newTable = (LinkedList<Entry>[])new LinkedList[_capacity * factor];;
        
        for (int i = 0; i < _capacity; i++)
        {
            LinkedList<Entry> bucket = getBucket(i);
            
            if (bucket != null)
            {
                for (Entry entry: bucket)
                {
                    insert(newTable, entry.getValue());
                }
            }
        }
        
        _table = newTable;
        
	_threshold = (int)(factor * _capacity * _loadFactor);
        _capacity *= factor;
    }
    
    /**
     * Inserts a value
     * @param value Value to insert
     */
    public void insert(int value)
    {
        if (_size >= _threshold)
        {
            expandHashtable();
        }
        
        insert(_table, value);
        
        _size++;
    }
    
    /**
     * Inserts a value into a LinkedList<Entry>[]
     * @param table The table
     * @param value Value to insert
     */
    private void insert(LinkedList<Entry>[] table, int value)
    {
        int hash = hashValue(value, table.length);
        
        if (table[hash] == null)
        {
            table[hash] = new LinkedList<Entry>();
        }
        
        table[hash].add(new Entry(value));
    }
    
    /**
     * Removes a value
     * @param value Value to remove
     * @return true if this list contained the specified element
     */
    public boolean remove(int value)
    {
        int hash = hashValue(value);
        
        LinkedList<Entry> bucket = getBucket(hash);
        
        if (bucket != null)
        {
            // If there is a bucket and that buckets contains an element with
            // the value, remove the element, decrement the number of elements
            // and return true
            if (bucket.remove(new Entry(value)))
            {
                _size--;
                return true;
            }
        }
        
        // If the element can't be found, return false
        return false;
    }
    
    /**
     * Get the capacity of the table
     * @return The capacity
     */
    public int getCapacity()
    {
        return _capacity;
    }
    
    /**
     * Get number of buckets
     * @return The size
     */
    public int getSize()
    {
        return _size;
    }
    
    /**
     * Get an element
     * @param index Index of the bucket
     * @return The bucket if exists, else null
     */
    public Entry getElement(int value)
    {
        int hash = hashValue(value);
        
        LinkedList<Entry> bucket = getBucket(hash);
        
        if (bucket != null)
        {
            for (Entry entry: bucket)
            {
                if (entry.getValue() == value)
                {
                    return entry;
                }
            }
        }
        
        return null;
    }
    
    /**
     * Gets number of comparisons needed to find a specific element
     * @param value The searched value
     * @return The number of comparisons
     */
    public int getSearchComparisons(int value)
    {
        int hash = hashValue(value);
        // Starting with one, since "bucket != null" is already a comparison
        int i = 1;
        
        LinkedList<Entry> bucket = getBucket(hash);
        
        if (bucket != null)
        {
            for (Entry entry: bucket)
            {
                i++;
                if (entry.getValue() == value)
                {
                    return i;
                }
            }
        }
        
        return i;
    }
    
    /**
     * Get a bucket
     * @param index Index of the bucket
     * @return The bucket
     */
    public LinkedList<Entry> getBucket(int index)
    {
        if (index < 0 || index >= _capacity)
        {
            throw new IllegalArgumentException("getEntry: index out of range.");
        }
        
        return _table[index];
    }
    
    /**
     * Fills the hashtable with integers from 0 to (n - 1)
     * @param n Number of values
     */
    public void fillInOrder(int n)
    {
        if (n < 0)
        {
            throw new IllegalArgumentException("fillRandom: n must be positive.");
        }
        
        for (int i = 0; i < n; i++)
        {
            insert(i);
        }
    }
    
    /**
     * Fills the hashtable with random integers from 0 to capacity * 10
     * @param n Number of random values
     */
    public void fillRandom(int n)
    {
        fillRandom(n, 10);
    }
    
    /**
     * Fills the hashtable with random integers from 0 to capacity * multiplier
     * @param n Number of random values
     * @param multiplier The random value will be multiplied by this
     */
    public void fillRandom(int n, int multiplier)
    {
        if (n < 0)
        {
            throw new IllegalArgumentException("fillRandom: n must be positive.");
        }
        
        if (multiplier < 0)
        {
            throw new IllegalArgumentException("fillRandom: multiplier must be positive.");
        }
        
        for (int i = 0; i < n; i++)
        {
            insert((int)(Math.random() * _capacity * multiplier));
        }
    }
}